
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#include "../../sr_module.h"
#include "../../mem/shm_mem.h"

#include "hash.h"

static void hash_resize(HashTable *);

static unsigned int table_size[] = {
    7, 13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191,
    16381, 32749, 65521, 131071,
    262143, 524287, 1048575, 2097151, 4194303, 8388607,
    16777211, 33554431, 67108863, 134217727, 268435455,
    536870911, 1073741823, 2147483647, 0
};

/*
 * hash function: return unsigned int
 */
static unsigned int hash(HashTable *ht, const char *key) {
    unsigned int seed = 131;
    unsigned int hash = 0;

    while (*key) {
        hash = hash * seed + (*key++);
    }

    return (hash & 0x7FFFFFFF) % table_size[ht->size];
}

/*
 * create hash table: return HashTable
 */
HashTable *hash_create(unsigned int size) {

    HashTable *theTable;

    int i;

    theTable = (HashTable *)shm_malloc(sizeof(HashTable));
    if (theTable == NULL) {
        INFO( "Could not create HashTable. Out of memory/n");
        return NULL;
    }

    theTable->size = 0;
    theTable->used = 0;
    while (table_size[theTable->size] < size) {
        theTable->size++;
        if (table_size[theTable->size] == 0) {
            theTable->size--;
            break;
        }
    }

    theTable->ht = (HashNode **)shm_malloc(sizeof(HashNode *) * table_size[theTable->size]);
    if (theTable->ht == NULL) {
        shm_free(theTable);
        INFO( "Could not create HashTable. Out of memory/n");
        return NULL;
    }

    for (i = 0; i < size; i++)
        theTable->ht[i] = NULL;

    theTable->lock = lock_alloc();
    if (theTable->lock == NULL) {
        shm_free(theTable);
        INFO( "Could not create HashTable. Out of memory/n");
        return NULL;
    }

    // The lock
    if(NULL == lock_init(theTable->lock)) {
        ERR("Could not init the lock");
        lock_dealloc(theTable->lock);
        shm_free(theTable);
        return NULL;
    }

    return theTable;
}

int hash_free(HashTable *theTable) {
    int size;
    HashNode *node, *next;

    if (!theTable) return -1;

    size = theTable->size - 1;
    for (; size >= 0; size--) {
        node = theTable->ht[size];

        //shm_free hash node
        while (node) {
            next = node->next;
            shm_free((void *)node->key);
            shm_free(node->value);
            shm_free(node);
            node = next;
        }
    }

    lock_destroy(theTable->lock);
    lock_dealloc(theTable->lock);
    shm_free(theTable->ht);
    shm_free(theTable);

    return 0;
}

/*
 * Put the key-value pair in the hashtable.
 * It will NOT check if the key exists already.
 */
int hash_put(HashTable *theTable, char *key, void *value) {
    unsigned int h;
    size_t len;
    HashNode *node;

    if (theTable->used > table_size[theTable->size])
        hash_resize(theTable);

    node = (HashNode *)shm_malloc(sizeof(HashNode));
    if (!node) {
        INFO( "Could not put element. Out of memory/n");
        return -1;
    }

    len = strlen(key) + 1;
    node->key = (char *)shm_malloc(len);
    if (!node->key) {
        shm_free(node);
        return -1;
    }

    strcpy(node->key, key);
    node->value = value;

    h = hash(theTable, node->key);
    if (!theTable->ht[h]) {
        node->next = NULL;
        theTable->ht[h] = node;
    } else {
        node->next = theTable->ht[h];
        theTable->ht[h] = node;
    }

    theTable->used++;

    return 0;
}


void *hash_get(HashTable *theTable, char *key) {
    unsigned int h;
    HashNode *node;

    h = hash(theTable, key);
    node = theTable->ht[h];

    while (node && (strcmp(key, node->key) != 0)) {
        node = node->next;
    }

    if (node == NULL) {
        return (void *)NULL;
    } else {
        return node->value;
    }
}

int hash_remove(HashTable *theTable, char *key) {
    HashNode *node, *prev;
    unsigned int h;

    h = hash(theTable, key);
    node = prev = theTable->ht[h];

    while (node && (strcmp(key, node->key) != 0)) {
        prev = node;
        node = node->next;
    }

    if (node == NULL) {
        return -1;
    } else {
        if (node == theTable->ht[h]) {
            theTable->ht[h] = node->next;
        } else {
            prev->next = node->next;
        }
        shm_free(node->key);
        shm_free(node->value);
        shm_free(node);

        theTable->used--;
    }

    return 0;
}

static void hash_resize(HashTable *h_old) {
    HashTable ht;
    int i;
    if (table_size[h_old->size + 1] == 0) return;

    ht.used = h_old->used;
    ht.size = h_old->size + 1;
    ht.ht = (HashNode **)shm_malloc(sizeof(HashNode *) * table_size[ht.size]);
    if (!ht.ht) {
        INFO("failed to shm_malloc hashtable./n");
        return;
    }

    /*
      traverse the old hash table entries and re-link them into their
      new places in the new table.
    */
    for (i = 0; i < table_size[h_old->size]; i++) {
        HashNode *e = h_old->ht[i];
        HashNode *next_e;
        while (e) {
            unsigned int hashval = hash(&ht, e->key);//hash key
            next_e = e->next;//save next node

            e->next = ht.ht[hashval]; //--+
            //  |---- swap
            ht.ht[hashval] = e;       //--+

            e = next_e;
        }
    }

    /* overwrite the old with the new */
    shm_free(h_old->ht);
    h_old->ht = ht.ht;
    h_old->size = ht.size;
    //printf("resize hashtable/n");
}

void hash_dump(HashTable *ht, dumpfunc print) {
    unsigned int size = table_size[ht->size];
    int i;

    for (i = 0; i < size; i++) {
        HashNode *e = ht->ht[i];
        while (e) {
            print((void *)e);
            e = e->next;
        }
    }
}

int hash_getSize(HashTable *theTable) {
    return table_size[theTable->size];
}

void hash_print(HashTable *theTable) {
    LM_INFO("====== Printing the HashTable ======");
    unsigned int size = table_size[theTable->size];
    int i;

    for (i = 0; i < size; i++) {
        HashNode *entry = theTable->ht[i];
        while (entry) {
            LM_INFO("key=%s, value=%d", entry->key, *((int *)(entry->value)));
            entry = entry->next;
        }
    }
    LM_INFO("************************************");
}
